package No101_200.No151_160.IntersectionofTwoLinkedLists_160;

public class Solution {
	
	public static void main(String[] args) {
		ListNode l10 = new ListNode(1);
		ListNode l11 = new ListNode(3);
		ListNode l12 = new ListNode(5);
		ListNode l13 = new ListNode(6);
		ListNode l14 = new ListNode(7);
		ListNode l15 = new ListNode(8);
		ListNode l16 = new ListNode(9);
		ListNode l17 = new ListNode(10);
		l10.next = l11;l11.next = l12;l12.next = l13;l13.next = l14;l14.next = l15;
		l15.next = l16;l16.next = l17;//l12.next = l13;l13.next = l14;l14.next = l15;
		ListNode l20 = new ListNode(2);
		ListNode l21 = new ListNode(4);
		ListNode l22 = new ListNode(6);
		ListNode l23 = new ListNode(7);
		ListNode l24 = new ListNode(8);
		ListNode l25 = new ListNode(9);
		ListNode l26 = new ListNode(10);
		l20.next = l21;l21.next = l22;l22.next = l23;l23.next = l24;l24.next = l25;
		l25.next = l26;
		System.out.println(getIntersectionNode(l10,l20).val);
	}
	
	public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
		ListNode h1 = headA;
		ListNode h2 = headB;
		if(headA == null ||headB == null)return null;  
		int lengthA = 1;
		int lengthB = 1;
		while (headA.next!=null || headB.next!=null) {
			if (headA.next!=null) {
				lengthA++;
				headA = headA.next;
			}
			if (headB.next!=null) {
				lengthB++;
				headB = headB.next;
			}
		}
		if(headA.val != headB.val) return null;  
		int num = (lengthA>lengthB)?1:2;
		if (num == 1) {
			for (int i = 0; i < lengthA-lengthB; i++) {
				h1 = h1.next;
			}
			for (int i = 0; i < lengthB; i++) {
				if (h1.val == h2.val) {
					return h1;
				}
				h1 = h1.next;h2 = h2.next; 
			}
		}else {
			for (int i = 0; i < lengthB-lengthA; i++) {
				h2 = h2.next;
			}
			for (int i = 0; i < lengthA; i++) {
				if (h1.val == h2.val) {
					return h1;
				}
				h1 = h1.next;h2 = h2.next; 
			}
		}
		
		return null;
    }
}


class ListNode {
	int val;
	ListNode next;
	ListNode(int x) {
		val = x;
		next = null;
	}
}
